Numerically Controlled Machining
Simulating the process of numerically controlled (NC) machining is of fundamental importance in computer aided design (CAD) and computer aided manufacturing (CAM). During simulation, a computer model of a workpiece is edited with a computer representation of an NC machining tool and a set of NC machining tool motions to simulate the machining process.
The workpiece model and tool representation can be visualized during the simulation to detect potential collisions between parts, such as the workpiece and the tool holder, and after the simulation to verify the final shape of the workpiece.
The final shape of the workpiece is affected by the selection of the tool and the tool motions. Instructions for controlling these motions are typically generated using the CAM system from a graphical representation of the desired final shape of the workpiece. The motions are typically implemented using numerical control programming language, also known as preparatory code or G-Codes, see the following standards RS274D and DIN 66025/ISO 6983.
The G-Codes generated by the CAM system may not produce an exact replication of the desired shape. In addition, the movement of the NC tool is governed by motors of the NC machining machine, which have predetermined speeds, accelerations, ranges of motion, so that the actual tool motions may not exactly follow the NC machine instructions.
Discrepancies between the actual final-shape of the workpiece and the desired shape of the workpiece may be very small. In some situations, these discrepancies can result in undesirable gouges or nicks in the surface of the final shape of the workpiece with sizes on the order of a few micrometers in depth and width, and tens of micrometers in length.
Typically, a set of NC machine instructions are tested by machining a test workpiece made of softer, less expensive material prior to machine the workpiece. If visual inspection of the test workpiece locates undesirable discrepancies in the test workpiece, then the NC machine instructions can be modified accordingly.
This manual testing is time consuming and expensive. Time for machining a single test workpiece may be on the order of hours and several iterations may be required before an acceptable set of NC machine instructions is attained.
Thus, it is desirable to test for these discrepancies using computer-based simulation and rendering. However, in order to detect discrepancies with dimensions on the order of a few micrometers for workpieces, which may have dimensions on the order of meters, very precise computer models are required.
Swept Volumes
During machining, a tool moves relative to the workpiece according to a prescribed tool motion, referred to herein as a tool path, where the tool path can contain information about the relative position, orientation, and other shape data of the tool with respect to the workpiece.
As the tool moves along the tool path, the tool carves out a “swept volume.” During machining, as the tool moves along the tool path, a portion of the workpiece that is intersected by the swept volume is removed. This material removal can be modeled in the computer as a constructive solid geometry (CSG) difference operation, in which the portion of the workpiece is removed from the workpiece using a CSG subtraction operation on the swept volume and the workpiece.
To provide high precision machining simulation, it is necessary to have a precise representation of the swept volume. Thus, it is an object of the present invention to provide a space and time efficient method for representing and rendering high precision models of swept volumes.
Although NC machining simulation is used as an example herein, swept volumes have applications in many areas of science, engineering, entertainment, and computer graphics. Some specific applications include computer-aided design, freeform design, computer-based drawing, animation, solid modeling, robotics, manufacturing automation, and visualization to name but a few. The following description applies to all areas where an accurate representation of a swept volume is required or desired.
Although NC machining simulation usually performs in three-dimensional coordinate systems, the term ‘swept volume’ can be extended more generally to N-dimensional coordinate systems. In particular, the following description also applies to areas swept out by a one-dimensional or two-dimensional shape moving along a path in a two-dimensional space, or to a hyper-volume swept out by a shape moving over a path or surface in higher dimensional spaces.
An overview of the importance and challenges in swept volume research is presented in “Swept Volumes: Foundations, Perspectives, and Applications”, International Journal of Shape Modeling, 2006, Abdel-Malek, Blackmore, and Joy. They conclude that research in this field is limited by the difficulty of implementing complex mathematical formulations of sweeps in computer software and that computing the boundaries of swept volumes remains a challenging problem requiring better visualization tools and more accurate methods.
The swept volumes of simple shapes moving along simple paths can sometimes be represented analytically, as described in U.S. Pat. No. 4,833,617. However, those methods do not generalize to complex shapes and complex tool paths.
Several approaches approximate the swept volumes of polygonal shapes. Models of polygonal shapes can be encoded in a spatial hierarchy for efficient editing via the CSG operations as in “Interactive CSG” Proceedings, Technical Sketches, SIGGRAPH, 1999, Butcher, or for efficient collision detection as in U.S. Pat. No. 6,099,573.
A method for approximating the swept volume of a polygonal object is described in “Computing Swept Volumes”, Journal of Visualization and Animation, 2000, Abrams and Allen.
U.S. Pat. No. 6,862,560 describes a method for simulating machining using CSG operations on polygonal models of swept volumes. In that method, the boundary of the workpiece is encased in a set of cells, where each cell contains references to swept volume polygons that intersect the cell. Intersections between the workpiece and the swept volume polygons within a particular cell can be processed on demand to generate a high precision rendering of the machined surface in a small region of interest. However, visualizing the full model at high precision is prohibitively slow. In addition, the generation of the swept volumes and the processing of the intersections are not described.
U.S. Pat. No. 6,993,461 describes representing an object as a polyhedron. The object is placed along the path at discrete time steps using a series of transformations. Edges and faces of the polyhedral representation that lie on the boundary of the swept volume are determined at each time step, and connected to generate a polyhedral approximation of the swept volume.
The accuracy of each of these polygonal methods is limited by the polygonal representation of the object model. Billions of polygons may be required to accurately represent the curved surface of a complex tool, especially if the radius of curvature is small. Thus, those methods either have limited accuracy or they have prohibitive processing times and memory requirements for generating high precision models of swept volumes or both. In addition, methods that approximate the swept volume as a series of discrete time steps have limited precision between the time steps, and are subject to aliasing artifacts.
Another common representation for machining simulation is known as the Z-buffer (depth) or Dexel method. That approach is described in “Real-time Shaded NC Machining Display”, Proceedings, SIGGRAPH 1986, van Hook. U.S. Pat. No. 7,149,668 describes a similar method in which the workpiece is modeled by a grid of straight lines all in the z-direction and the machining simulation is performed by moving the tool model over the grid and modifying the height of the lines representing the workpiece that are intersected by the tool.
Dexel methods typically suffer from limited resolution, especially in directions not aligned with the z-axis, and are not suitable for generating high precision models of swept volumes.
Dexel representations are related to voxel-based representations. In “Volume Visualization,” IEEE Computer Society Press, 1991, Kaufman describes voxel-based representations, as well as methods for rendering and processing voxel-based representations. In “Sculpting: an Interactive Volumetric Modeling Technique”, Proceedings, SIGGRAPH 1991, Galyean and Hughes, and “Volume Sculpting:, Proceedings, SIGGRAPH 1995, Wang and Kaufman, both simulate sculpting using CSG operations on voxel-based representations of objects.
Methods that use binary voxels to represent swept volumes include U.S. Pat. No. 6,044,306, and “Method and Apparatus for Shaping Geometric Shapes” and “Octree-based Boundary Evaluation for General Sweeps”, Proceedings, TMCE, 2008 Erdim and Ilies. Those methods both have accuracy limited by the size of the smallest voxel used to represent the swept volumes.
Distance Fields
Distance fields are an effective representation for rendering and editing shapes, as described in U.S. Pat. Nos. 6,396,492, 6,724,393, 6,826,024, and 7,042,458. Specifically, the distance fields are a form of implicit functions that are used to represent an object. A distance field is a scalar field that gives the shortest distance to the surface of the object from any point in space. A point at which the distance field is zero is on the surface of the object. The set of points on the surface of the object collectively describe the boundary of the object, also known as the d=0 isosurface. The distance field of an object is usually signed such that the sign of the distance field for a point inside the object is opposite the sign of the distance field for a point outside the object. For example, the distance field has a positive sign for points inside the object, and a negative sign for points outside the object.
Distance fields can be used to represent and render swept volumes. In “Sweeping of Three Dimensional Objects”, Computer Aided Design, 20(4), 1990, Martin and Stephenson, described a theoretical foundation for defining the envelope of a swept volume in terms of an implicit function. In “Function Representation for Sweeping by a Moving Solid”, Proceedings, Solid Modeling, 1995, Sourin and Pasko represented swept volumes using implicit surfaces. However, implicit surfaces can be difficult to render, and a suitable implicit representation for an arbitrarily complex tool shape is difficult to define.
A procedure for computing the distance field of an object is called a distance field function. For very simple objects, such as a plane, a sphere or a cylinder, the distance field function can be an analytic function with a closed form. For more complex objects an analytic function may not be possible. However, a numerical procedure may still be possible. For example, U.S. patent application Ser. No. 12/468,607 describes a numerical procedure for determining the distance field of a swept object, such as a swept machining tool.
For still more complex objects, there may not be a simple numerical procedure that can be used to compute the distance field of the object. For example, a machined workpiece can have a very complex surface such that a numerical procedure cannot compute the distance field of the object. In this case, the distance field of the object can be computed by sampling and reconstruction.
Sampling involves determining and storing values of the distance field at a set of locations in space. Reconstruction uses the stored values and a reconstruction function to compute the distance field of the object at points where the distance field was not sampled. A common approach to sampling is to sample the values of the distance field on a regular 3D grid of locations (regular sampling) that are evenly spaced. A common 3D reconstruction function is trilinear reconstruction where the eight samples that surround a point are combined together using a trilinear interpolation function to compute the value of the distance field at the point.
Regular sampling of a distance field is very simple, but may not be very efficient. The shape of the object may be such that there are regions in space where the distance field changes slowly and there are many very similar samples such that an accurate distance field could be reconstructed with far fewer samples (over sampled). Likewise, there may be regions of space where the distance field is changing quickly such that the number of samples is not sufficient to accurately reconstruct the distance field (under-sampled).
Adaptively sampled distance fields (ADFs) use detail-directed sampling to provide a much more space and time efficient representation of distance fields than is obtained using regular sampling. A type of ADF called a sampled ADF stores the samples of the value of the distance field in a spatial hierarchy of cells where the size of the cells, which is inversely related to a density of samples, is smaller where the distance field changes rapidly, and larger in regions where the distance field changes slowly. By using a locally varying density of samples, a sampled ADF avoids over-sampling some regions and under-sampling other regions. Each cell of the sampled ADF contains distance field samples and is associated with a reconstruction method for reconstructing the portion of the distance field associated with the cell. Distance field samples can include the values of the distance field, as well as the gradients and partial derivatives of the distance field. The distance field within a cell can be reconstructed from the distance data samples only when needed to minimize memory and processing time.
Sampled ADFs that store sample values of the distance field of the object provide a useful way to trade-off model accuracy with memory requirements. The accuracy of the reconstructed distance field is related to the number of distance field samples within a cell, as well as the reconstruction function, and the size of the cell. The accuracy of the reconstructed distance field can be increased in a number of ways: the number of samples in a cell could be increased, or the amount of information associated with each sample could be increased, or the size of the cell could be decrease.
For example, a triquadric reconstruction function is more accurate than a trilinear reconstruction function but requires 27 scalar distance field samples, whereas the trilinear reconstruction function only requires 8 scalar distance field samples, a more than 3-fold increase in the data per cell. Alternatively, the minimum cell size in the ADF can be reduced to increase accuracy, but this also increases memory since the number of cells needed to fill a given volume will also increase. However, to obtain very high accuracy (˜1 micron) using a sampled ADF can require a prohibitively large amount of memory and processing time when simulating a large workpiece.
ADFs can be used to simulate editing using CSG operations. The model to be edited and the editing tool can be represented as distance functions, regularly sampled distance fields, or ADFs. The editing process can generate the ADF of the edited shape explicitly, for example by modifying the ADF of the model.
Alternatively, the edited shape can be represented implicitly as a composite ADF. The composite adaptively sampled distance field (CADF) is generated to represent the object, where the composite ADF includes a set of cells arranged in a spatial hierarchy. Each cell in the composite ADF includes a subset of the set of geometric element distance field functions and a procedural reconstruction method for combining the subset of geometric element distance field functions to reconstruct a composite distance field of a portion of the object represented by the cell. Each distance field in the subset of distance fields forms a part of the boundary of the object within the cell, called the composite boundary.
A procedure for determining the subset of the set of geometric element distance field functions within a cell should only include in the subset those distance field functions whose boundaries form parts of the composite boundary within the cell. The procedure for determining the subset must be fast but also accurate or the resulting composite boundary will not be correct. For example, a ray sampling procedure, such as described in U.S. patent application Ser. No. 12/751,591, can be used. However, the ray sampling procedure can result in errors in the determination of the subset of distance field that cannot be easily detected.
Composite ADFs can reconstruct the distance field of a machined object with very high accuracy. The distance field function of the set of geometric elements can be computed with high accuracy by analytic or numerical methods and their values combined also with high accuracy. The resulting surface is very detailed with surface features that may be smaller than 1 micron for a simulated object that is in the order of 1 cubic meter. However, the reconstruction of this very accurate surface can be slow limiting the usability of the method.
Thus, there is a need to improve on the existing method used to determine the subset of the set of geometric element distance fields within the cells of a composite ADF to reduce errors in the reconstructed composite boundary of the object. Additionally, there is a need for a method to improve the speed of reconstruction of the composite boundary of the object to improve the usability of the composite ADF representation.